/**
 * 105. 从前序与中序遍历序列构造二叉树（与 剑指 Offer 07 同）
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
public class Solutions_105 {
    public static void main(String[] args) {
//        int[] preorder = {3, 9, 20, 15, 7};  // 前序遍历
//        int[] inorder = {9, 3, 15, 20, 7};  // 中序遍历
//         output: {3, 9, 20, null, null, 15, 7}

//        int[] preorder = {1, 2, 3};  // 前序遍历
//        int[] inorder = {2, 1, 3};  // 中序遍历
        // output: {1, 2, 3}

        int[] preorder = {-1};  // 前序遍历
        int[] inorder = {-1};  // 中序遍历
        // output: {-1}

        TreeNode result = buildTree(preorder, inorder);
        System.out.println(result);
    }

    private static int in = 0;
    private static int pre = 0;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int stop = Integer.MAX_VALUE;
        return buildTree(preorder, inorder, stop);
    }

    /**
     * 中序遍历（左中右）时，对当前遍历元素的前一元素分析
     * 左子节点的前一元素为父节点的父节点
     * 右子节点的前一元素为父节点
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder, int stop) {
        if (pre >= preorder.length) {
            // 结束条件
            return null;
        }
        if (inorder[in] == stop) {
            // 区间分治终止条件
            in ++;
            return null;
        }
        int rootVal = preorder[pre++];
        // 创建根节点，并以 rootVal 在中序遍历数组 inorder 中的位置，完成左右子树的构造
        TreeNode root = new TreeNode(rootVal);
        // 构造左子树时，若 in 所在的节点就是根节点，则 root 没有左子树
        root.left = buildTree(preorder, inorder, rootVal);
        // 构造右子树时，若 in 所在的节点就是父节点的父节点，即 stop 节点，则 root 没有右子树
        root.right = buildTree(preorder, inorder, stop);
        return root;
    }
}
